package cp;

/**
 * Created by 程程有小棉被啊 on 2020年12月09日.
 */
public class LeetCode_11 {

    /*
        盛水最多的
            给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点(i,ai) 。
            在坐标内画 n 条垂直线，垂直线 i的两个端点分别为(i,ai) 和 (i, 0) 。
            找出其中的两条线，使得它们与x轴共同构成的容器可以容纳最多的水。
        示例：
            输入：[1,8,6,2,5,4,8,3,7]
            输出：49
     */


    public static void main(String[] args) {
        int[] num = {1, 8, 6, 2, 5, 4, 8, 3, 7};
        System.out.println(mostWater(num));
        System.out.println(mostWater2(num));
    }

    //由两边向中间收拢（夹逼准则）
    static int mostWater(int[] num) {
        int mostWater = 0;
        for (int i = 0, j = num.length - 1; i < j; ) {
            //计算当前最大的面积
            int mostNow = (j - i) * Math.min(num[i], num[j]);//长度取最小的进行计算
            if (num[i] < num[j]) {
                i++;
            } else {
                j--;
            }
            //判断首尾的元素，每次移动最小的元素
            mostWater = Math.max(mostWater, mostNow);
        }
        return mostWater;
    }

    static int mostWater2(int[] num) {
        int maxWater = 0;
        for (int i = 0, j = num.length - 1; i < j; ) {
            int maxNow = Math.min(num[i],num[j]) * (j- i);
            if (num[i] < num[j]){
                i++;
            }else{
                j--;
            }
            maxWater = Math.max(maxNow,maxWater);
        }
        return maxWater;
    }


}
